import scala.math.abs



object ND 
{
  sealed abstract class List[+A] 
  {
    def head: A
    def tail: List[A]
  }

  final class Cons[A](hd: A, tl: => List[A]) extends List[A] 
  {
    override val head: A = hd
    override lazy val tail: List[A] = tl
  }

  object Cons
  {
    def apply[A](hd: A, tl: => List[A]) = new Cons(hd, tl)
    def unapply[A](c: Cons[A]) = Some(c.head, c.tail)
  }
  case object Nil extends List[Nothing] 
  {
    override def head: Nothing = 
    {
      throw new NoSuchElementException("head of empty list")
    }
    override def tail: List[Nothing] = 
    {
      throw new NoSuchElementException("tail of empty list")
    }
  }

  def nat(x: Int): List[Int] = Cons(x, nat(x + 1))

  def map_wrong[A, B](f: A => B)(l: => List[A]): List[B] = l match 
  {
    case Nil => Nil
    case Cons(head, tail) => Cons(f(head), map(f)(tail))
  }

  def map[A, B](f: A => B)(l: => List[A]): List[B] = l match 
  {
    case Nil => Nil
    case c: Cons[A] => Cons(f(c.head), map(f)(c.tail))
  }

  def imperative_squareroot(a0: Double, eps: Double, n: Double): Double = 
  {

    var x = a0
    var y = a0 + 2 * eps
    while (abs(x - y) > eps) 
    {
      y = x
      x = (x + n/x) / 2
    }
    x
  }

  def next(n: Double)(x: Double): Double = (x + n/x) / 2

  def repeat[A](f: A => A, a: A): List[A] = Cons(a, repeat(f, f(a)))

  def within(eps: Double, l: List[Double]): Double = 
  {
    val a = l.head
    if (a.isNaN) throw new RuntimeException("nan")
    val rest = l.tail
    val b = rest.head
    if(abs(a - b) <= eps) b else within(eps, rest)
  }

  def sqrt(a0: Double, eps: Double, n: Double) = within(eps, repeat(next(n), a0))


  def relative(eps: Double, l: List[Double]): Double = 
  {
    val a = l.head
    if (a.isNaN) throw new RuntimeException("nan")
    val rest = l.tail
    val b = rest.head
    if(abs(a - b) <= eps * abs(b)) b else relative(eps, rest)
  }

  def relativesqrt(a0: Double, eps: Double, n: Double) =
  relative(eps, repeat(next(n), a0))

  def easydiff(f: Double => Double, x: Double)(h: Double): Double =
  (f(x + h) - f(x)) / h


  def differentiate(h0: Double, f: Double => Double, x: Double) =
  map(easydiff(f, x))(repeat(halve, h0))
  def halve(x: Double) = x / 2

  def elimerror(n: Double, l: List[Double]): List[Double] = 
  {
    val a = l.head
    val bandrest = l.tail
    val b = bandrest.head
    Cons(
    (b * math.pow(2.0, n) - a) / (math.pow(2.0, n) - 1.0),
    elimerror(n, bandrest))
  }


  def order(l: List[Double]): Double = 
  {
    val LOG2: Double = math.log(2.0)
    def log2(x: Double) = math.log(x) / LOG2

    val a = l.head
    val b = l.tail.head
    val c = l.tail.tail.head
    val o = math.round(log2((a-c)/(b-c) - 1))
    if (o == 0) 1 else o
  }


  def improve(s: List[Double]): List[Double] = elimerror(order(s), s)

  def superimprove(s: List[Double]): List[Double] = map(second)(repeat(improve, s))
  def second(l: List[Double]): Double = l.tail.head

  def superdifferentiate(f: Double => Double, x: Double): Double = 
  {
    val eps: Double = 0.00000001
    within(eps, superimprove(differentiate(x + 2 * eps, f, x)))
  }
}
